Best Time to Buy and Sell Stock II

LeetCode 122 | Difficulty: Medium

Medium

Problem Description

You are given an integer array prices where prices[i] is the price of a given stock on the i^th day.

On each day, you may decide to buy and/or sell the stock. You can only hold at most one share of the stock at any time. However, you can sell and buy the stock multiple times on the same day, ensuring you never hold more than one share of the stock.

Find and return the maximum profit you can achieve.

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Total profit is 4.

Example 3:

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: There is no way to make a positive profit, so we never buy the stock to achieve the maximum profit of 0.

Constraints:

- `1 <= prices.length <= 3 * 10^4`

- `0 <= prices[i] <= 10^4`

Topics: Array, Dynamic Programming, Greedy

---

Approach

Dynamic Programming

Break the problem into overlapping subproblems. Define a state (what information do you need?), a recurrence (how does state[i] depend on smaller states?), and a base case. Consider both top-down (memoization) and bottom-up (tabulation) approaches.

When to use

Optimal substructure + overlapping subproblems (counting ways, min/max cost, feasibility).

Greedy

At each step, make the locally optimal choice. The challenge is proving the greedy choice leads to a global optimum. Look for: can I sort by some criterion? Does choosing the best option now ever hurt future choices?

When to use

Interval scheduling, activity selection, minimum coins (certain denominations), Huffman coding.

---

Solutions

Solution 1: C# (Best: 112 ms)

Metric	Value
Runtime	112 ms
Memory	22.8 MB
Date	2019-02-21

Solution

public class Solution {
    public int MaxProfit(int[] prices) {
            
    int profit = 0;
    for (int i = 1; i < prices.Length; i++)
    {
        profit += Math.Max(prices[i]-prices[i-1],0);
    }   
    return profit;  
    }
}

📜 2 more C# submission(s)

Submission (2019-02-21) — 112 ms, 23.1 MB

public class Solution {
    public int MaxProfit(int[] prices) {
            if(prices.Length==0) return 0;
    int profit = 0;
    for (int i = 1; i < prices.Length; i++)
    {
        profit += Math.Max(prices[i]-prices[i-1],0);
    }   
    return profit;  
    }
}

Submission (2020-04-06) — 160 ms, 25.2 MB

public class Solution {
    public int MaxProfit(int[] prices) {
            
    int profit = 0;
    for (int i = 1; i < prices.Length; i++)
    {
        profit += Math.Max(prices[i]-prices[i-1],0);
    }   
    return profit;  
    }
}

---

Complexity Analysis

Approach	Time	Space
Dynamic Programming	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Define the DP state clearly. Ask: "What is the minimum information I need to make a decision at each step?"
• Consider if you can reduce space by only keeping the last row/few values.